package com.dylan.历史.算法;

/**
 * @Auther: ankang
 * @Date: 2019/1/29 11:04
 * @Description:
 */
public class 背包0_1_回溯法 {

    public static void main(String[] args) {
        f(0, 0, new int[]{1, 1, 5, 5, 5, 10, 10}, 7, 34);
        System.out.println("maxW=" + maxW);
    }

    private static int maxW = Integer.MIN_VALUE;

    /**
     * 0-1背包问题
     * @param i 表示考察到哪个物品了
     * @param cw 表示当前已经装进去的重量总和
     * @param items 表示每个物品重量
     * @param n 表示物品个数
     * @param w 背包可承受重量
     */
    private static void f(int i, int cw, int[] items, int n, int w) {
        if (cw == w || i == n) { // cw==w 表示装满了；i==n 表示已考察完所有物品
            if (cw > maxW) {
                maxW = cw;
            }
            return;
        }
        f(i + 1, cw, items, n, w);
        if (cw + items[i] <= w) { // 如果超出背包可承受重量，则不再装了
            f(i + 1, cw + items[i], items, n, w);
        }
    }

}
